#include <stdio.h>

char table[5000050] = {0};
int results[5000050] = {0};

void prepare_table() {
    for (int i = 2; i < 2237; i == 2 ? (i = 3) : (i += 2)) {
        for (int n = i; n < 5000050; n += i) {
            if (i != n) table[n] = 1;
        }
    }
    table[0] = 1;
    table[1] = 1;
    table[2] = 1;
    int res = 0;
    for (int i = 0; i < 5000040; i++) {
        if (i == 1 || i == 0 || i == 2) {
            results[i] = 0;
            continue;
        }
        if (table[i] == 0 && table[i + 2] == 0) {
            res++;
        }
        results[i] = res;
    }
}

int prime_count(int start, int end) {
    //printf("%d %d!\n", results[end], results[start]);
    return results[end] - results[start];
}

int main(void) {
    prepare_table();
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        //printf("%d %d ", a, b);
        if (b - a < 2) {
            printf("0\n");
        } else {
            printf("%d\n", prime_count(a - 1, b - 2));
        }
    }
    return 0;
}
